package leecode

import (
	"math"
)

func findPrimePairs(n int) [][]int {

	var result [][]int
	for i := 1; i <= n/2; i++ {
		if isPrime2761(i) && isPrime2761(n-i) {
			result = append(result, []int{i, n - i})
		}
	}
	return result
}

// 判断是否是质数
func isPrime2761(n int) bool {
	if n <= 3 {
		return n > 1
	}
	//只有6x - 1 和 6x + 1 的数才有可能是质数
	if n%6 != 1 && n%6 != 5 {
		return false
	}
	sqrt := int(math.Sqrt(float64(n)))
	for i := 5; i <= sqrt; i += 6 {
		if n%i == 0 || n%(i+2) == 0 {
			return false
		}
	}
	return true
}
